package fr.cephb.util;

import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.RandomAccessFile;
import java.util.Comparator;
import java.util.Random;

public class MergeSort
	{
	private Comparator<byte[]> comparator;
	private int sizeof;
	private int buffer_capacity=1000000;
	
	private class TmpBuff
		{
		private byte buffer[];
		
		int fill(RandomAccessFile in) throws IOException
			{
			this.buffer=null;
			byte tmp[]=new byte[MergeSort.this.sizeof];
			int chunck_read=0;
			ByteArrayOutputStream baos= new ByteArrayOutputStream(MergeSort.this.buffer_capacity);
			while(chunck_read*sizeof< getBufferCapacity() && chunck_read<2)
				{
				int nRead=0;
				int n;
				while((n=in.read(tmp,nRead,tmp.length-nRead))!=-1)
					{
					nRead+=n;
					if(nRead==tmp.length) break;
					}
				if(nRead==0) break;
				baos.write(tmp);
				++chunck_read;
				}
			baos.flush();
			this.buffer=baos.toByteArray();
			if(this.buffer.length!=sizeof*chunck_read) throw new AssertionError();
			QuickSort qSort=new QuickSort(sizeof,comparator);
			qSort.quicksort(this.buffer);
			return chunck_read;
			}
		}
	
	private class TmpFile
		{
		File file;
		//int size;
		}
	
	public MergeSort(int sizeof,Comparator<byte[]> comparator)
		{
		if(sizeof<=0) throw new IllegalArgumentException("Bad sizeof:"+sizeof);
		this.sizeof=sizeof;
		this.comparator=comparator;
		}
	
	public MergeSort(int sizeof)
		{
		this(sizeof,null);
		}
	
	public void sort(File file) throws IOException
		{
		if(!file.exists()) throw new FileNotFoundException(file.toString());
		if(!file.isFile()) throw new IOException("Not a file: "+file.toString());
		
		long file_length=file.length();
		if(file_length%this.sizeof!=0)
			{
			throw new IOException("bad file size (file.length="+file_length+")%"+sizeof+"!=0");
			}
		RandomAccessFile fin=new RandomAccessFile(file,"rw");
		fin.seek(0L);
		try
			{
			TmpFile copyFile=null;
			TmpBuff buffer=new TmpBuff();
			while(buffer.fill(fin)>0)
				{
				TmpFile dest=new TmpFile();
				dest.file=File.createTempFile("_sort", ".tmp", file.getParentFile());
				FileOutputStream out= new FileOutputStream(dest.file);
				if(copyFile==null)
					{
					out.write(buffer.buffer);
					}
				else
					{
					FileInputStream in=new FileInputStream(copyFile.file);
					merge(buffer.buffer,in,out);
					in.close();
					}
				out.flush();
				out.close();
				
				TmpFile tmp=copyFile;
				copyFile=dest;
				if(tmp!=null) tmp.file.delete();
				}
			if(copyFile!=null)
				{
				int n_write=0;
				fin.seek(0L);
				FileInputStream in= new FileInputStream(copyFile.file);
				byte tmp[]=new byte[sizeof];
				while(readFully(in,tmp,0,sizeof))
					{
					fin.write(tmp);
					++n_write;
					}
				in.close();
				copyFile.file.delete();
				System.err.println("copied to original "+n_write);
				}
			fin.close();
			}
		catch(IOException e)
			{
			throw e;
			}
		finally
			{
			fin.close();
			}
		}
	
	
	
	private void merge(byte buffer[],FileInputStream in,OutputStream out)
		throws IOException
		{
		int index_in_byte_array=0;
		byte tmp1[]=new byte[sizeof];
		byte tmp2[]=new byte[sizeof];
		boolean need_reload_1=true;
		boolean need_reload_2=true;
		while(true)
			{
			
			boolean ok_1=true;
			boolean ok_2=true;
			
			if(need_reload_1)
				{ 
				if(index_in_byte_array*sizeof<buffer.length)
					{
					System.arraycopy(buffer, index_in_byte_array*sizeof, tmp1, 0, sizeof);
					index_in_byte_array++;
					}
				else
					{
					ok_1=false;
					}

				}
			
			if(need_reload_2)
				{
				if(!readFully(in,tmp2,0,sizeof))
					{
					ok_2=false;
					}
				}
			if(!ok_1 && !ok_2)
				{
				need_reload_1=false;
				need_reload_2=false;
				break;
				}
			if(ok_1 && !ok_2)
				{
				out.write(tmp1);
				need_reload_1=true;
				need_reload_2=false;
				break;
				}
			if(!ok_1 && ok_2)
				{
				out.write(tmp2);
				need_reload_1=false;
				need_reload_2=true;
				break;
				}
			
			int cmp=compare(tmp1,tmp2);
			if(cmp==0)
				{
				out.write(tmp1);
				out.write(tmp2);
				need_reload_1=true;
				need_reload_2=true;
				}
			else if(cmp<0)
				{
				out.write(tmp1);
				need_reload_1=true;
				need_reload_2=false;
				}
			else
				{
				out.write(tmp2);
				need_reload_1=false;
				need_reload_2=true;
				}
			}
		
		while(need_reload_1)
			{ 
			if(index_in_byte_array*sizeof>=buffer.length)
				{
				break;
				}
			System.arraycopy(buffer, index_in_byte_array*sizeof, tmp1, 0, sizeof);
			out.write(tmp1);
			index_in_byte_array++;
			}
		
		while(need_reload_2)
			{
			if(!readFully(in,tmp2,0,sizeof))
				{
				break;
				}
			out.write(tmp2);
			}
		
		}
	
	private boolean readFully(InputStream in,byte array[],int index,int len)
		throws IOException
		{
		int nRead=0;
		int n;
		while((n=in.read(array,index+nRead,len-nRead))!=-1)
			{
			nRead+=n;
			if(nRead==len) break;
			}
		if(nRead==0) return false;
		if(nRead!=len) throw new IOException("Failed to read "+len);
		return true;
		}
	
	private int compare(byte cmp_array_1[],byte cmp_array_2[])
		{
		if(this.comparator!=null)
			{
			return comparator.compare(cmp_array_1,cmp_array_2);
			}
		int i=0;
		while(i<sizeof)
			{
			int a=cmp_array_1[i];
			int b=cmp_array_2[i];
			if(a!=b)
				{
				return a-b;
				}
			i++;
			}
		return 0;
		}
	
	
	public void setBufferCapacity(int bufferCapacity)
		{
		buffer_capacity = bufferCapacity;
		}
	public int getBufferCapacity()
		{
		return buffer_capacity;
		}
	
	private void echo(File f)
	throws IOException
	{
	System.err.println("ECHO:");
	RandomAccessFile in=new RandomAccessFile(f, "r");
	byte buff[]=new byte[this.sizeof];
	for(int i=0;i< LIMIT;++i)
		{
		in.seek(i*sizeof);
		in.readFully(buff);
		if(i<100 || i>LIMIT-100
				
		) System.err.println(new String(buff));
		}
	
	in.close();
	}
	
	
	static final int LIMIT=20000;
	static final int SIZEOF_TEST=7;
	public static void main(String[] args)
	throws Exception
		{
		File f=new File("/home/pierre/jeter.bin");//File.createTempFile("_qsort", ".bin");
		if(f.exists()) f.delete();
		//f.deleteOnExit();
		Random rand= new Random();
		
		RandomAccessFile out=new RandomAccessFile(f, "rw");
		for(int i=0;i< LIMIT;i++)
			{
			StringBuilder b= new StringBuilder();
			for(int j=0;j<SIZEOF_TEST-1;++j)
				{
				b.append((char)('A'+rand.nextInt(26)));
				}
			b.append('.');
			out.write(b.toString().getBytes());
			}
		
		out.close();
		MergeSort q= new MergeSort(SIZEOF_TEST);
		q.echo(f);
		System.err.println("Sort...");
		q.sort(f);
		q.echo(f);
		System.err.println("2nd ");
		q.sort(f);
		q.echo(f);
		System.err.println("Sort...");
		q= new MergeSort(SIZEOF_TEST,new Comparator<byte[]>()
			{
			@Override
			public int compare(byte[] o1, byte[] o2)
				{
				return new String(o2).compareToIgnoreCase(new String(o1));
				}
			});
		q.sort(f);
		q.echo(f);
		
		f.delete();
		System.err.println("Done");
		}
	
	}

